package treesNgraphs;

/**
 * Created by Tzachi on 13/10/2014.
 *
 * Write an algorithm to find the ‘next’ node (e.g., in-order successor)
 * of a given node in a binary search tree where each node has a link to its parent.
 *
 *
 *              10
 *            /   \
 *           7     14
 *               /   \
 *             11    16
 *
 *  1. If X has a right child, then the successor must be on the right side of X (because of the order in which we visit nodes). Specifically, the left-most child must be the first node visited in that subtree.
 *  2. Else, we go to X’s parent (call it P).
 *  2.a. If X was a left child (P.left = X), then P is the successor of X
 *  2.b. If X was a right child (P.right = X), then we have fully visited P, so we call successor(P).
 *
 */

public class InOrderSuccessor {

    public static TreeNode inorderSucc(ParentTreeNode e) {
        if (e != null) {
            ParentTreeNode p;
            // Found right children -> return 1st inorder node on right
            if (e.parent == null || e.getRightChild() != null) {
                p = (ParentTreeNode) leftMostChild(e.getRightChild());
            } else {
                // Go up until we’re on left instead of right (case 2b)
                while ((p = e.parent) != null) {
                    if (p.getLeftChild() == e) {
                        break;
                    }
                    e = p;
                }
            }
            return p;
        }
        return null;
    }

    public static TreeNode leftMostChild(TreeNode e) {
        if (e == null) return null;
        while (e.getLeftChild() != null) e = e.getLeftChild();
        return e;
    }

    public static class ParentTreeNode extends TreeNode {
        ParentTreeNode parent;

        public ParentTreeNode(int value) {
            super(value);
        }

        public TreeNode getParent() {
            return parent;
        }
    }
}
